/*
 * @lc app=leetcode.cn id=1584 lang=javascript
 *
 * [1584] 连接所有点的最小费用
 */

// @lc code=start
/**
 * @param {number[][]} points
 * @return {number}
 */
var minCostConnectPoints = function (points) {
  const size = points.length;
  const uf = new UnionFind(size);
  const edges = [];

  for (let i = 0; i < size; i++) {
    for (let j = i + 1; j < size; j++) {
      edges.push([dist(i, j, points), i, j]);
    }
  }
  // 按照距离升序
  edges.sort((a, b) => a[0] - b[0]);

  let result = 0;
  let num = 1;
  for (const [dist, x, y] of edges) {
    // 新连通
    if (uf.union(x, y)) {
      result += dist;
      num++;
      // points中点全部遍历完毕
      if (num === size) {
        break;
      }
    }
  }
  return result;

  function dist(x, y, points) {
    return (
      Math.abs(points[x][0] - points[y][0]) +
      Math.abs(points[x][1] - points[y][1])
    );
  }
};

class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((_, idx) => idx);
  }
  find(x) {
    if (x !== this.parent[x]) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(x, y) {
    const ux = this.find(x);
    const uy = this.find(y);
    if (ux ^ uy) {
      // 新连通
      this.parent[ux] = uy;
      return true;
    }
    // 已连通
    return false;
  }
}
// @lc code=end
